/**
 * https://leetcode.cn/problems/insert-interval/
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）
 *
 * @param intervals
 * @param newInterval
 */
function insert(intervals: number[][], newInterval: number[]): number[][] {
  const newIntervals: number[][] = [];
  let [left, right] = newInterval;

  let merged = false
  for (const interval of intervals) {
    const [intervalLeft, intervalRight] = interval;

    if (intervalLeft > right) {
      if (!merged) {
        // 防止重复加入
        newIntervals.push([left, right]);
        merged = true
      }
      newIntervals.push(interval);
    } else if (intervalRight < left) {
      newIntervals.push(interval)
    } else {
      //! 存在交集，计算交集，不加入到 newIntervals中
      left = Math.min(left, intervalLeft)
      right = Math.max(right, intervalRight)
    }
  }

  if (!merged) {
    newIntervals.push([left, right])
  }

  return newIntervals;
}
